The present invention relates to a method of adding and verifying an electronic signature added to document data in order to authenticate the validity of the document data and a system using this method and, more particularly, to a method of effectively preventing alteration of document data, and a system using this method.
In recent years, systems for electronically converting (encoding) document information represented by E-mails and transmitting/receiving the encoded document information are very popular. The received electronic document information is normally accumulated in a magnetic recording medium or the like and can be partially cited.
Documents are generally classified into those having contents that can be accessed by only authorized parties and those having contents that can be accessed by indefinite parties. For example, the former documents correspond to electronic document information having contents associated with confidentiality of individual business enterprises and personal privacy. The latter documents correspond to electronic document information having contents that a business enterprise, a person, or a public organization intends to inform the third party of events and information. The electronic document information of the former document can be encrypted and kept secret from a person who does not have a decryption key. The electronic document information of the latter document is a free access plaintext.
The contents of the electronic document information of the latter document may be illicitly altered because this information is normally a plaintext. In particular, public information (electronic information) is often the target for a grapevine or information alteration. If such an illicit act happens, the social influence becomes serious.
To verify that the contents of an electronic document are not altered, electronic signature data is added to the electronic document, as needed. This electronic signature data verifies that "an electronic document with the electronic signature is indeed drafted by a public organization and is not illicitly altered information or a grapevine".
The principle of an electronic signature will be described by taking an E-mail as an example.
FIG. 19 shows a conventional processing flow of an E-mail to which an electronic signature is applied.
(1) When sending a data text to a receiver, the transmitting side compresses the data text to generate a digest (compressed text), encrypts the digest with the secret key of the transmitting side to generate data (compressed encrypted text) called a digital signature, adds the digital signature to the data text, and transmits the resultant data.
(2) The receiving side uses a public key corresponding to the secret key of the transmitting side to decrypt the digital signature data added to the data text, thereby obtaining the original digest data. At the same time, the receiving side compresses the received data text to generate digest data. The receiving side then compares these two digest data and can determine whether the data text is correct.
As described above, the electronic signature has (1) a message verification function of guaranteeing that information is not altered and is correct as original information, and (2) an entity verification function of guaranteeing that an entity A (e.g., person A) engaged in actions such as generation, transmission, processing, storage, and determination of information is actually the entity A.
More specifically, assume that some problem is posed between the entity A and an entity B on information written by the entity A. In this case, the electronic signature has (1) a function of allowing the B side to verify that indeed the sender of the message at issue is A, and the entity B can exhibit an evidence which explicitly indicates this fact, and (2) a function of inhibiting B from drafting a "counterfeit" message and asserting that the "sender of this message is A".
The signature data generation sequence on the transmitting side will be described in detail with reference to FIG. 20.
A whole text 1001 is converted into a compressed text 1003, i.e., the digest 1003 by conversion processing using a hash function 1002.
The hash function is a one-way function for converting digital data having an arbitrary length into digital data having a fixed length. According to the characteristic features of the hash function, it is very difficult to estimate the original data from the converted data, and the converted data is an unpredictable random number. By these features, long digital data need not be entirely signed by encryption. When the fixed-length digital data, i.e., the message digest generated by the hash function is encrypted, an effect equivalent to signature of the entire data can be expected. A known hash function is MD5 (reference: RFC1321 The MD5 Message-Digest Algorithm).
The digest 1003 is encrypted using information known to only a user himself as a key 1004. A key used here is a secret key of asymmetric key encryption scheme. In particular, RSA is most popular.
A signature 1005 generated as described above is transmitted together with the text (1006 in FIG. 19) and verified on the receiving side.
The RSA scheme will be briefly described.
The RSA is a system devised by R. L. Rivest, A. Shamir, and L. Adleman. This technique depends on modulo exponents. A parameter pair consisting of a public exponent and an arithmetic modulo are defined as a public key, whereas a parameter pair consisting of a secret exponent and an arithmetic modulo are defined as a secret key. This asymmetric algorithm uses the following symbols and abbreviations:
X, Y: data block smaller than arithmetic modulo PA1 n: arithmetic modulo PA1 e: public exponent PA1 d: secret exponent PA1 p, q: prime number; product of prime numbers p and q is arithmetic modulo (n) PA1 lcm: least common multiple PA1 mod n: arithmetic modulo n and uses the exponential functions for transferring a data block: PA1 Y=X e mod n (where, 0.ltoreq.X&lt;n) PA1 X=Y d mod n (where, 0.ltoreq.Y&lt;n) PA1 ed mod lcm (p-1, q-1)=1 or PA1 ed mod (p-1) (q-1)=1 PA1 dividing the document data into a plurality of divided document data using as a delimiter a predetermined character appearing in a document represented by the document data; PA1 generating an electronic signature for each of the divided document data on the basis of the divided document data; and PA1 storing the divided document data, the electronic signature based on the divided document data, and information for associating the divided document data with the electronic signature. PA1 storing the document data upon excluding a predetermined character appearing in a document represented by the document data; PA1 generating an electronic signature on the basis of the document data from which the predetermined character is excluded; and PA1 storing the document data from which the predetermined character is not excluded, the electronic signature, and information for associating the electronic signature with the document data from which the predetermined character is not excluded. PA1 obtaining a total number of printable characters in the document data and a total number of unprintable characters in the document data; and PA1 evaluating reliability on the basis of the total numbers of printable and unprintable characters.
For example, these functions are satisfied by the following solutions:
In order to validate this processing, the data block must be interpreted as an integer.
In this case, (e, n) is disclosed to the public, and d is the secret key. The digest is encrypted using the secret key d in the signature. Anyone can generate a digest, but it is very difficult to derive the secret key d from the disclosed (e, n). For this reason, in fact, only the user himself who knows the secret key d can affix the signature. However, since (e, n) is disclosed to the public and these parameters satisfy the above predetermined calculation expressions, anyone can decrypt the encrypted signature and verify the signature.
The signature verification sequence on the receiving side will be described in detail with reference to FIG. 21.
The receiving side generates digest 1 (1011 in FIG. 21) from a predetermined hash function 1002 from the text of a received message 1006 with a signature. By using an RSA public key 1010, the receiving side decrypts the signature added to the text to generate digest 2 (1012 in FIG. 21) as a compressed text generated by the writer of the text. Digests 1 and 2 are compared with each other (1013). If digest 1 coincides with digest 2, the text is a message drafted by the person who appended the signature (1014); otherwise, it is possible to detect a wrong signature or alteration of the message (1015).
The electronic signature can prevent alteration of documents, and reliability of the contents of documents can be maintained.
Various problems are posed by the conventional electronic signature method described above.
The first problem is experienced when part of an E-mail text is cited and the cited portion is transmitted.
More specifically, according to the conventional electronic signature method, an electronic signature is added to a whole text. When a given block of the text is cited, the electronic signature is of no use for the cited block. That is, one often wants to cite a paragraph as a block of an E-mail text, which has a meaning by itself and is verifiable not to have been altered. Even in this case, an electronic signature of the writer cannot be added to the given paragraph according to the conventional method. For example, when only the given paragraph is cited and transferred to a third party, the third party cannot verify the source of the given paragraph.
More specifically, as shown in FIG. 22, assume that an electronic signature X is added to a message consisting of messages 1, 2, and 3 written by the entity A, and the resultant data is transferred to the entity B. Thereafter, the entity B cites only message 2 from the message written by the entity A and writes a message consisting of messages a, 2, and b, adds an electronic signature Y to them, and sends the resultant data to an entity C (it is assumed that the message a describes that the writer of message 2 is A). In this case, the entity C cannot verify whether the writer of message 2 is A as the entity B maintains.
In order to avoid the above inconvenience, in the above detailed example, to allow the entity B to transfer only message 2 to the entity C, the entire message consisting of messages 1, 2, and 3, and its electronic signature must be transferred, resulting in inconvenience.
The second problem is posed when an E-mail text is edited and transferred.
More specifically, assume that the whole message is cited. In this case, when editing involving no character printing is performed, i.e., when a line return or a blank (space) is entered amidst the document, the conventional electronic signature mechanism detects that the document has been altered, although the meaning of the document has not been changed. Under these circumstances, it is very useful detecting that the document is not altered when the meaning of the document has not been changed.
The third problem is posed when a document is intentionally altered.
A person who intends to alter a document devises the altering method so that the message digest of the altered document matches the message digest before alteration. For this purpose, for example, an unprintable character can be used.
More specifically, if several unprintable characters are inserted in this document in altering a document, it may be possible to generate the same message digest as in the document before alteration, although the meaning of the document is altered.
For example, the "fee is 10,000 yen." is altered to the "fee is 100,000 yen." When this altered document is converted by a hash function to generate a digest, the digest does not coincide with that of the digest of the document before alteration, thereby detecting alteration. To the contrary, when an unprintable character such as a space (.sub.--) is inserted in the altered document to obtain the "fee is.sub.-- 100,000 yen." or the "fee is.sub.-- 100,000 yen..sub.-- ", a digest which may coincide with the original digest can be found. In this case, the system determines that no alteration is made. Since the space is not printed, alteration cannot be found upon visual observation.
Conventionally, on the receiving side of a document added with an electronic signature, no clue has been given as to the possibility of the above alteration or reliability of the document.